package graph;

import java.util.*;

/**
 * @author Liaorun
 */
public class Kruskal {


    public static class MySets {
        public HashMap<Node, List<Node>> setMap;


        public MySets(Collection<Node> nodes) {

            for (Node cur : nodes) {
                // 开一个数组
                ArrayList<Node> set = new ArrayList<>();
                // 把节点放进去
                set.add(cur);

                // 把节点和数组的关系记录下来
                setMap.put(cur, set);
            }
        }

        /**
         * 两个节点是否在同一个集合
         *
         * @param from 一个节点
         * @param to   另一个节点
         * @return true or false
         */
        public boolean isSameSet(Node from, Node to) {
            List<Node> fromSet = setMap.get(from);
            List<Node> toSet = setMap.get(to);

            return fromSet == toSet;
        }

        public void union(Node from, Node to) {
            List<Node> fromSet = setMap.get(from);
            List<Node> toSet = setMap.get(to);

            for (Node toNode : toSet) {
                // 将toSet的所有值放到fromSet
                fromSet.add(toNode);
                // 修改这些节点属于的集合的记录
                setMap.put(toNode, fromSet);
            }
        }


        @Override
        public int hashCode() {
            return super.hashCode();
        }

        @Override
        public boolean equals(Object obj) {
            return super.equals(obj);
        }
    }

    public static class EdgeComparator implements Comparator<Edge> {

        @Override
        public int compare(Edge o1, Edge o2) {
            return o1.weight - o2.weight;
        }
    }

    /**
     * 生成图的最小生成树算法
     *
     * @param graph 图
     * @return 最小生成树需要的边
     */
    public static Set<Edge> kruskalMinimumSpanningTree(Graph graph) {
        MySets mySets = new MySets(graph.nodes.values());

        // 使用小顶堆排序获取最小的边
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());

        // 将所有的边放到小顶堆中
        priorityQueue.addAll(graph.edges);

        // 记录最后需要的边的无序集合
        Set<Edge> result = new HashSet<>();

        while (!priorityQueue.isEmpty()) {

            // 取出权值最小的边
            Edge edge = priorityQueue.poll();

            // 边连接的两个点在不在一个集合
            if (!mySets.isSameSet(edge.from, edge.to)) {
                // 不在就可以要这条边
                result.add(edge);
                // 将边连接的两个点放到一个集合
                mySets.union(edge.from, edge.to);
            }
        }
        return result;
    }
}
